Матч 381, Игра с кубиком (TheDiceGame)

Дивизион 2, Уровень 2

У Джона есть стандартный игральный кубик с 6 гранями. Каждый раз после его бросания Джон получает от мамы столько конфет, сколько выпадет косточек на верхней грани. Мальчик хочет узнать, сколько раз ему необходимо бросать кубик, чтобы суммарно получить от мамы не менее candies конфет.

Класс: TheDiceGame

Метод: double expectedThrows(int candies)

Ограничения: 1 ≤ candies ≤ 1000000.

Вход. Желаемое количество конфет candies.

Выход. Ожидаемое количество бросков кубика.

Пример входа

candies

1

2

7

47

Пример выхода

1.0

1.1666666666666667

2.5216263717421126

13.90476189046144

РЕШЕНИЕ

динамическое программированике + вероятность

Пусть r[i] содержит количество бросков, необходимое для получения в точности i конфет. Очевидно, что r[0] = 0, а также r[i] = 0 при i < 0.

Для i > 0 имеем соотношение:

На кубике может выпасть число от 1 до 6. Для получения в точности i конфет можно, например, получить i – k (1 ≤ k ≤ 6) конфет, после чего бросить кубик и с вероятностью 1 / 6 получить еще k конфет.

Последовательно вычисляем значения r[i] для i от 1 до candies и возвращаем r[candies].

ПРОГРАММА

#include <stdio.h>

#define max(a,b) (a)>(b)?(a):(b)

double r[1000001];

class TheDiceGame

{

public:

double expectedThrows(int candies)

{

int i, j;

double s;

r[0] = 0;

for(i = 1; i <= candies; i++)

{

for(s = 0, j = max(i-6,0); j < i; j++)

s += r[j];

r[i] = 1 + s / 6;

}

return r[candies];

}

};